\documentclass[12pt,a4paper,oneside]{article}


\usepackage{graphicx}
\usepackage{paralist}

\usepackage[brazil]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{url}

%opening
\title{Relatório Trabalho Prático 1 : \\Algoritmos Genéticos para Otimização e Aprendizado de Máquina}
\author{Ramon Pereira Lopes \\ Rangel Silva Oliveira}

\begin{document}

\maketitle

\section{Introdução}

O presente documento refere-se ao relatório do trabalho prático da disciplina de Computação Natural. O trabalho prático em questão consiste em implementar Algoritmos Genéticos (AG) para um problema de otimização, especificamente o problema de resolução de labirintos, e para um problema de aprendizado de máquina. Adicionalmente, o presente trabalho consiste em implementar um arcabouço para AG, de modo que este seja utilizado nas soluções propostas. Para fins de implementação, a linguagem Java foi adotada, sendo que, ao final dessa etapa, execuções (experimentos) foram conduzidas a fim de avaliar a sensibilidade dos parâmetros em cada problema.

\section{Implementação}

\subsection{Arcabouço}

Como um dos objetivos deste trabalho, um arcabouço para algoritmos genéticos foi implementado. De um modo geral, o arcabouço implementado pode ser visto como um conjunto de componentes reusáveis que permite sua instanciação para diversas cenários. As Figuras \ref{fig:diagrama:individuo} e     \ref{fig:diagrama:algoritmo} apresentam os componentes constituintes do arcabouço implementado.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{diagrama-individuo.png} 
  \caption{Diagrama de classes que representa a classe referente ao indivíduo no arcabouço implementado.}
    \label{fig:diagrama:individuo}
\end{figure}

A classe \textit{IndividuoGA}, apresentada na Figura \ref{fig:diagrama:individuo}, modela o indivíduo do algoritmo genético no arcabouço implementado. A classe em questão é constituída pelos atributos: \begin{inparaenum}[i)]
  \item genome[] - representa o genótipo do indivíduo, de tal modo que, para fins de generalização, este foi representado por um vetor de \textit{double}.
  \item fitness - representa a \textit{fitness} do indivíduo, cuja representação no indivíduo foi uma decisão de projeto norteada pela inexistência de componente que possua como responsabilidade calcular a fitness dos indivíduos.
\end{inparaenum} 
Por fim, a classe possui métodos abstratos que possibilitam a instanciação (uso) do arcabouço em uma aplicação específica. Vale ressaltar que tais métodos abstratos devem ser implementados na instanciação do arcabouço. A classe é constituída pelos métodos:
\begin{inparaenum}[i)]
  \item mutacao - método abstrato que tem por função realizar a operação de mutação no indivíduo.
  \item crossOver - método abstrato que como objetivo realizar a operação \textit{crossover} entre dois indivíduos, sendo um deles passado como parâmetro para o método.
\end{inparaenum} 

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{diagrama-algoritmo.png} 
  \caption{Diagrama de classes que representa a classe referente ao algoritmo genético no arcabouço implementado.}
    \label{fig:diagrama:algoritmo}
\end{figure}


A classe \textit{GeneticAlgorithmGA}, apresentada na Figura \ref{fig:diagrama:algoritmo}, modela a estrutura de uma classe responsável pelo algoritmo genético. Para fins didáticos, tal classe pode ser vista como um \textit{engine} da aplicação. A classe em questão é constituída pelos atributos: 
\begin{inparaenum}[i)]
  \item cruzamento - representa a probabilidade de ocorrência de cruzamento entre dois indivíduos.
  \item mutação - representa a probabilidade de ocorrência de mutação.
  \item gerações - indica o número de gerações alcançado pelo algoritmo genético.
  \item torneio - indica o tamanho do torneio.
  \item elitismo - indica se o critério de elitismo será aplicado na execução algoritmo.
  \item tamanhoPopulacao - indica o tamanho da população, que se manterá fixo ao longo do algoritmo.
  \item pior - armazena a quantidade de filhos, oriundos de \textit{crossover}, com \textit{fitness} pior que a \textit{fitness} média de seus pais.
  \item melhor - armazena a quantidade de filhos, oriundos de \textit{crossover}, com \textit{fitness} melhor que a \textit{fitness} média de seus pais.
\end{inparaenum} 
A classe é composta pelos seguintes métodos:
\begin{inparaenum}[i)]
  \item operador - método que recebe dois indivíduos como parâmetro e realiza operadores de mutação e \textit{crossover}.
  \item torneio - método que recebe a população atual e, com base no parâmetro de torneio, seleciona o melhor indivíduo.
\end{inparaenum}
Vale ressaltar que os métodos supracitados são concretos, isto é, já têm suas respectivas implementações, embora seja possível os sobrescrever.

Como citado anteriormente, não existe componente algum responsável pelo cálculo da \textit{fitness} de um indivíduo. Tal decisão de projeto foi tomada devido à alta dependência entre o cálculo da \textit{fitness} e a aplicação, dificultando tanto o projeto quanto a implementação de um componente reutilizável para tal fim.

\subsection{Otimização - Labirinto}

O problema do Labirinto caracteriza um problema de otimização no qual deseja-se obter o menor caminho entre os pontos de saída e chegada. A representação através do algoritmo genético foi feita da seguinte forma:

O genoma é representado por um arranjo de \textit{byte}, em que cada posição representa um possível movimento do indivíduo no tabuleiro. O tamanho do arranjo é o mesmo do número de células do tabuleiro. Esta decisão foi adotada para facilitar as trocas de informação entre indivíduos.

Para se gerar um indivíduo, gera-se aleatoriamente um conjunto de passos do tamanho do genoma. Esses passos podem ser N, S, L, O e não é levado em consideração que os passos feitos em sequencia levem a uma solução viável, é possível que um indivíduo atravesse uma parede a fim de procurar um menor caminho. Este problema é solucionado aplicando uma penalidade na \textit{fitness} de cada indivíduo que não respeita o critério de passos válidos.

No cruzamento, os indivíduos trocam partes do genoma um com o outro, sem haver nenhuma restrição de viabilidade de solução. Na mutação ocorre algo semelhante no sentido de que nenhuma verificação de viabilidade é feita, apenas a função \textit{fitness} vai levar em consideração os passos válidos de um indivíduo em direção ao seu destino.

A função \textit{fitness} usa todas as posições do genoma com a intenção de forçar o indivíduo a dar passos válidos em direção a sua meta. Os passos inválidos intermediários são penalizados e não deslocam o indivíduo no tabuleiro, mas no final só os passos válidos comporão a solução obtida por ele.

O fato de não restringir indivíduos a terem apenas soluções válidas tem por objetivo promover uma melhor busca no espaço de soluções.

\subsection{Aprendizado}

Devido ao bom projeto realizado na implementação do arcabouço, o problema de aprendizado foi instanciado no arcabouço sem grandes dificuldades. Para tal fim, foram criadas classes para representar o indivíduo e o algoritmo genético (\textit{engine}) da aplicação estendendo aquelas já fornecidas pelo arcabouço. 

A classe que representa o indivíduo sobrescreveu os métodos de mutação, o qual consiste em alterar uma posição do genótipo, e de \textit{crossover}, que consiste em gerar dois novos filhos por meio de um particionamento e junção do material genético dos pais. Vale ressaltar que o indivíduo foi representado por meio do vetor de \textit{double}, já fornecido pelo arcabouço, composto por três posições referentes ao peso de cada classificador. Em suma, não houve problemas para o mapeamento do indivíduo da aplicação para o arcabouço, de modo que apenas foi necessário definir os métodos abstratos deste.

A classe que representa o algoritmo genético (\textit{engine}) da aplicação foi implementada de modo a reusar o métodos providos pela classe equivalente no arcabouço. Adicionalmente, alguns métodos auxiliares foram implementados, dentre os quais destacam-se: método para aceitação cuja critério foi fixado em indivíduos com \textit{fitness} maior ou igual a 0,5; método para geração da população inicial; método de controle de geração da nova população, no qual foi utilizado um regime de substituição permanente foi adotado, como também, caso o critério de elitismo seja adotado, 10\% dos melhores indivíduos pertencerão à nova população.

No problema em questão, o cálculo da \textit{fitness} foi realizado sobre uma dada partição. Em outras palavras, um indivíduo e um conjunto de dados (partição) são fornecidos para o módulo de cálculo de \textit{fitness}, o qual computará a acurácia, sinônimo de \textit{fitness} ao longo desta seção, de tal indivíduo sobre o conjunto de dados especificado. É possível notar que, com base no problema anterior, o cálculo de \textit{fitness} é totalmente diferente, corroborando a decisão de projeto de não representar tal módulo no arcabouço.

\section{Experimentos}

\subsection{Otimização - Labirinto}

A função \textit{fitness} leva em consideração uma série de fatores para definir seu valor de forma justa a comparar os indivíduos na população. Os valores apresentados consideram as penalidades impostas, podendo ser bastante elevados, mas representam fielmente o comportamento do algoritmo ao longo se dua execução.

A Figura \ref{fig:parte2mut} apresenta os resultados para a variação da mutação para o algoritmo genético aplicado ao Labirinto. A representação do genoma para o indivíduo foi feita de forma a representar apenas a direção de um determinado passo. Tal fato impõe uma certa dificuldade ao algoritmo no que diz respeito ao contexto de cada um. Na mutação todas as posições do genoma possuem a probabilidade de ser mudada ou não. Pelos resultados foi possível perceber que a melhor configuração seria de $50\%$ de mutação. Essa taxa alta se explica pelo que foi mencionado anteriormente.

\begin{figure}[!h]
  \centering
  	\includegraphics[scale=0.5]{Mutacao_maze.png} 
  \caption{Impacto da variação da mutação em (\%).}
    \label{fig:parte2mut}
\end{figure}

A Figura \ref{fig:parte2cross} mostra o comportamento do algoritmo para as probabilidades de \textit{crossover} entre os indivíduos. O \textit{crossover} se mostrou melhor ao passo que a probabilidade de mutação vai aumentando, sendo que a melhor configuração seria $80\%$. No cruzamento, parte do genoma é mantido intacto, tal fato possibilita ao indivíduo realizar mais passos válidos em direção ao destino.

\begin{figure}[!h]
  \centering
  	\includegraphics[scale=0.5]{Crossover_maze.png} 
  \caption{Impacto da variação do Crossover em (\%).}
    \label{fig:parte2cross}
\end{figure}

O tamanho da população favorece ao algoritmo uma maior diversidade na criação de indivíduos, portanto faz com que haja uma maior probabilidade de se gerar boas soluções. Por outro lado, com o aumento excessivo da população, acontece a geração de indivíduos repetidos que se tiverem uma \textit{fitness} ruim, mas forem selecionados no torneio, fazem com que o melhor indivíduo seja piorado no valor de sua \textit{fitness}.

\begin{figure}[!h]
  \centering
  	\includegraphics[scale=0.5]{Tamanho_maze.png} 
  \caption{Impacto da variação entre o tamanho da população em (\%).}
    \label{fig:parte2tam}
\end{figure}

\textbf{Exemplo de execução do algoritmo para o labirinto:}
\begin{verbatim}
# java ufmg.maze.main.Main -i ../input/M0.txt -c 80 -n 700 -p 700 -r 10 -m 50
Melhor solução encontrada: 22.0

# java ufmg.maze.main.Main -i ../input/M1.txt -c 80 -n 700 -p 700 -r 10 -m 50
Melhor solução encontrada: 26222.0

# java ufmg.maze.main.Main -i ../input/M2.txt -c 80 -n 1200 -p 1200 -r 20 -m 50
Melhor solução encontrada: 107678.0

# java ufmg.maze.main.Main -i ../input/M3.txt -c 80 -n 700 -p 700 -r 10 -m 50
Melhor solução encontrada: 438110.0
\end{verbatim}

\textit{Fitness} médio para a melhor configuração de parâmetros encontrada:

\begin{enumerate}
	\item \textbf{M0:} 22.00;
	\item \textbf{M1:} 26199.90;
	\item \textbf{M2:} 107561;
	\item \textbf{M3:} 398102.72.
\end{enumerate}

\subsection{Aprendizado}

A fim de configurar os parâmetros do algoritmo genético, diversos experimentos foram realizados. Para cada configuração dos experimentos, 30 execuções foram realizadas, de modo que os valores médios obtidos são reportados neste documento. É importante ressaltar que os experimentos foram conduzidos sobre conjunto de dados de aprendizado 1.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{parte1.pdf} 
  \caption{Impacto da variação entre o tamanho da população e o número de gerações do AG.}
    \label{fig:parte1}
\end{figure}


A  Figura \ref{fig:parte1} apresenta o impacto na \textit{fitness} média do melhor indivíduo por meio da variação entre o tamanho da população e o número de gerações do algoritmo genético. Por meio de tal gráfico, é possível constatar que o melhor resultado foi obtido com o tamanho da população igual a 250 indivíduos e o número de gerações igual a 500. Vale ressaltar que o objetivo deste conjunto de experimentos é justamente determinar o melhor valor para os parâmetros de tamanho da população e número de gerações. Para tal fim, os demais parâmetros foram fixados de tal forma: uso de elitismo, torneio de tamanho 2, probabilidade de \textit{crossover} 0.6 e de mutação 0.001.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{parte2.pdf} 
  \caption{Impacto da variação entre as probabilidades de mutação e \textit{crossover} no AG.}
    \label{fig:parte2}
\end{figure}

A Figura \ref{fig:parte2} apresenta o resultado do estudo de impacto da variação das probabilidades de \textit{crossover} e mutação na \textit{fitness} média do melhor indivíduo. Por meio dos experimentos realizados e de tal gráfico, é possível concluir que o melhor valor encontrado foi com as respectivas probabilidades de mutação e \textit{crossover} 0 e 0,5. Ao longo dos experimentos, os seguintes parâmetros foram adotados: uso de elitismo, tornio de tamanho 2; adicionalmente, os parâmetros de tamanho da população e número de gerações foram fixados com base nos resultados obtidos anteriormente.

\begin{figure}[htp]
  \centering
  	\includegraphics[scale=0.7]{parte3.pdf} 
  \caption{Impacto da variação do tamanho do torneio no AG.}
    \label{fig:parte3}
\end{figure}
   
A Figura \ref{fig:parte3} apresenta os resultados obtidos por meio da variação do tamanho do torneio. É possível constatar que o aumento do tamanho do torneio resulta em melhores indivíduos, de modo que, em consonância com tal constatação, o melhor resultado foi obtido com o valor de torneio igual a 100.

Por fim, com os parâmetros anteriores fixados, estudou-se o impacto do elitismo no AG. Foi possível constatar que o uso do elitismo resulta em melhores indivíduos, uma vez que a \textit{fitness} média do melhor indivíduo com elitismo foi igual a 0,7768 enquanto sem o mesmo foi de 0,7753.

Com base nos experimentos realizados e discutidos anteriormente, os parâmetros foram fixados da seguinte forma: uso de elitismo, probabilidade de \textit{crossover} 0,5, probabilidade de mutação 0, tamanho da população 250 e, por fim, número de gerações 500. Deste modo, o algoritmo genético foi executado sobre os dois conjuntos de aprendizado.

\begin{table}[htp]
\centering
\label{tab:resultados}
\begin{tabular}{ccccc}
\hline

Conjunto & Melhor  & Pior  & Média  & Desvio Padrão  \\
\hline
1  & 0,7768 & 0,5914 & 0,7059 & 0,0163 \\
2  & 0,7183 & 0,7086 & 0,7083 & 0,0196 \\

\hline
\end{tabular}
\caption{Análise do algoritmo genético sobre os conjuntos de dados disponibilizados para avaliação.}
\end{table}

A Tabela \ref{tab:resultados} apresenta os resultados obtidos pela execução do algoritmo genético, cujos parâmetros foram configurados, sobre os conjuntos de aprendizado disponibilizados. Para cada conjunto, a tabela em questão apresenta o valor da \textit{fitness} média do melhor indivíduo, \textit{fitness} média do pior indivíduo, \textit{fitness} média da população constituinte da última geração, e, por fim, o desvio padrão da \textit{fitness} média do melhor indivíduo.

\section{Conclusões}
Em relação ao algoritmo genético implementado para o problema do labirinto, O principal problema detectado na solução proposta pelo labirinto é que o contexto não é mantido quando os operadores de cruzamento são aplicados. Ao partir um indivíduo, para fornecer parte a outro, o restante dos passos podem não ser viáveis no contexto do outro indivíduo, o que acaba por não favorecer a convergência do algoritmo. Há vários algoritmos na literatura que resolvem o problema do labirinto de forma exata, tais como A* e caminho mínimo. Esses algoritmos usam a ideia de grafo para representar o tabuleiro, em que há uma aresta de uma célula para outra caso seja possível caminhar nessa direção no tabuleiro. É possível perceber então que neste caso o algoritmo genético não é tão recomendado para resolver tal problema, já que existem algoritmos polinomiais com a mesma finalidade.

Algoritmoss genéticos favorecem uma melhor busca no espaço de soluções, mas para isso é necessário uma boa caracterização da função \textit{fitness} a fim de promover uma melhor convergência. Baseado nisso, a representação genética do indivíduo é um fator determinante na implementação de uma boa solução.

Foi observado durante a implementação dos algoritmos que não é necessário definirmos um arcabouço complexo para geração de uma população inicial, assim como não é preciso propor um operador complexo para ser aplicado a cada indivíduo. Quanto mais simples, mais o problema é relaxado e o espaço de soluções é melhor analisado.

\bibliographystyle{plain}  % (uses file "plain.bst")
\bibliography{refs}     % expects file "myrefs.bib"

[1] Gordon, V.S. and Matley, Z. Evolving sparse direction maps for maze pathfinding. Pro-
ceedings of the IEEE Congress on Evolutionary Computation (CEC), 2004, Vol 1, 835–838.

[2] Thompson, S. Pruning boosted classifiers with a real valued genetic algorithm. Knowledge-
Based Systems, 1999, Vol. 12, Issues 5–6, 277–284.

\end{document}
